A computer network is a geographically distributed collection of interconnected subnetworks for transporting data between nodes, such as computers. A local area network (LAN) is an example of such a subnetwork; a plurality of LANs may be further interconnected by an intermediate network node, such as a router or switch, to extend the effective “size” of the computer network and increase the number of communicating nodes. The nodes typically communicate by exchanging discrete packets of data according to predefined protocols. The data packets transferred among the nodes may include fixed sized data cells and/or variable sized data frames. The packets typically comprise “payload” data prepended (“encapsulated”) by at least one network header formatted in accordance with a communication protocol, such as the Transmission Control Protocol/Internet Protocol (TCP/IP). In this context, a protocol consists of a set of rules defining how the nodes interact with each other.
Broadly stated, an intermediate network node is configured to exchange data packets between nodes connected to a wide range of communication links and subnetworks. To that end, the intermediate node implements a set of network services for the communicating nodes. The set of services may include route processing, path determination and path switching functions. The route processing function determines the type of routing needed for a received packet, whereas the path switching function allows the intermediate node to accept a packet on a first interface and forward it on a second interface. The path determination, or forwarding decision, function selects the most appropriate interface for forwarding a packet.
Forwarding decisions in an intermediate network node are typically performed by a forwarding engine in the node. The engine may be implemented in software, hardware or any combination thereof. For example, the engine may be embodied as software or firmware which is executable by an application specific integrated circuit (ASIC), field programmable gate array (FPGA), general-purpose processor, special-purpose processor, etc. A data packet is received at one of the node's network interfaces, e.g., coupled to a point-to-point link, Ethernet link, wireless link, optical link, etc. The node's network interface parses network headers from the packet and transfers them to the forwarding engine for processing. Notably, the headers may be processed in accordance with different layers of a network protocol stack, such as that described by the Open Systems Interconnection (OSI) Reference Model. For instance, the engine may be configured to operate at a data link layer (layer 2) or at a network protocol layer (layer 3) of the conventional OSI Model.
The forwarding engine makes a forwarding decision for a received packet header by examining a destination address contained in the header. The header typically includes, inter alia, source and destination addresses that identify the packet's sending and receiving nodes, respectively. Thus, the packet may “hop” from node to node, along an optimal network path, until it reaches its ultimate destination. Accordingly, the forwarding engine may route a packet to its next hop, replacing the media access control (MAC) layer-2 header of the packet as necessary.
The next hop for the packet is determined by routing information stored in the intermediate network node. Routing information is broadly understood to include any information, such as adjacency information, bridge-forwarding information, etc., used to implement the node's network services. The intermediate network node usually stores its routing information in data structures accessible to the forwarding engine. The routing information enables the engine to determine the next hop, and, in some cases, provide other services (quality-of-service, billing, etc.). In operation, the forwarding engine parses a destination address from a received packet header and performs an “address lookup” operation to determine whether any of the node's data structures contains routing information corresponding to the parsed address. If so, the next hop is chosen, and the packet is switched to the corresponding egress interface, with its layer-2 (MAC) information modified appropriately.
Often, layer-3 forwarding decisions performed in an intermediate network node are based on Internet Protocol Version 4 (IPv4) network addresses. According to the IPv4 address format, network addresses are represented as 32 bit (four byte) values, typically denoted by four numbers between 0 and 255. Thus, each interconnected subnetwork may be assigned a unique range of IPv4 addresses. For example, an exemplary subnetwork may be allocated the address space 212.47.101.*, where the asterisk is a wildcard that can differentiate up to 256 individual nodes in the subnetwork. For instance, a first node in the subnetwork may be assigned the address 212.47.101.1, whereas a second node may be assigned the address 212.47.101.2.
A subnetwork is often associated with a subnet mask that may be used to select a set of contiguous prefix bits from network addresses within the subnetwork's address space. The selected prefix bits are used, e.g., by an intermediate network node, to locate a route to the subnetwork. As used herein, a subnet mask length indicates the number of prefix bits selected by a subnet mask, and a subnet mask length of N bits is hereinafter represented as /N. For example, assume an exemplary subnetwork is associated with /25 network addresses. Therefore, the exemplary subnetwork may be associated with a subnet mask (e.g., 0xFFFFFF80) indicating that a prefix of the first 25 most-significant bits in a network address are required to locate a route to the subnetwork. Subnet masks and their uses are more generally described in Chapter 9 of the reference book entitled Interconnections Second Edition, by Radia Perlman, published September 1999, which is hereby incorporated by reference as though fully set forth herein.
Although it has performed well, several deficiencies have been identified with the IPv4 protocol. One of the primary deficiencies is its limited number of addresses. Specifically, IPv4's 32-bit addresses are expected to be exhausted in the next few years. As a result, work has been ongoing to develop a replacement for IPv4, namely the Internet Protocol Version 6 (IPv6). IPv6 addresses are 128 bits—four times longer than current IPv4 addresses—and consequently provide a significant increase in the number of available IP addresses. The IPv6 protocol and its addressing architecture are generally described by the Request for Comments (RFC) 2460 and 2373, respectively entitled Internet Protocol, Version 6 (IPv6) Specification and IP Version 6 Addressing Architecture, which are hereby incorporated by reference as though fully set forth herein.
Although IPv6 substantially increases the available IP address space, forwarding decisions based on 128-bit IPv6 addresses also consume more resources, such as memory, power or processing bandwidth, than those based on 32-bit IPv4 addresses. Conventional IPv4 address-lookup techniques, usually employed by a forwarding engine in an intermediate node, often cannot efficiently locate (i.e., “lookup”) routing information for IPv6 addresses. These previous IPv4 address-lookup techniques, which may be implemented using a radix trie (RTRIE), multiway trie (MTRIE), hash table, or content addressable memory (CAM), typically consume inordinate amounts of memory, power or processing resources when used to perform IPv6 address lookups.
For example, a forwarding engine may perform IPv6 address lookups by searching an RTRIE. An RTRIE is a type of binary trie whose “leaf” nodes contain pointers to other data structures storing routing information. “Trie”-type data structures are generally described in Chapter 13 of the reference book entitled Interconnections Second Edition, by Radia Perlman, which is hereby incorporated by reference as though fully set forth herein. Routing information for an IPv6 address may be located by searching an RTRIE on a bit-by-bit basis until the address's corresponding leaf node is found. The number of dependent lookups required to search the RTRIE typically depends on the number of address bits needed to differentiate between different addresses in the routing table. As used herein, a dependent lookup is broadly understood as a memory access operation that cannot be performed until a prior operation, such as a prior memory access, has been completed. Consequently, a sequence of dependent lookups must be performed sequentially.
By way of further example, suppose an RTRIE contains only two leaf nodes corresponding to the IPv6 addresses FFFF:: and FFFE::, so only one bit (i.e., the 16th most-significant bit, which is address bit 113) is needed to differentiate the addresses. Here (and hereinafter), the standard hexadecimal IPv6 address notation described in RFC 2373 is employed, where a double colon indicates a contiguous string of zeros. In this example, the leaf node for either address can be located by performing only one lookup in the RTRIE, e.g., based on the value of bit 113. If the address FFFD:: is added to the RTRIE, then two dependent lookups may have to be performed (e.g., based on bits 114 and 113). As additional IPv6 addresses are added to the RTRIE, the number of dependent lookups needed to locate an address's routing information increases.
When the RTRIE stores many more IPv6 addresses than in the above-described example, the number of dependent lookups performed in the RTRIE may become unreasonable. In the pathological case, 128 dependent lookups would have to be performed before an IPv6 address can be located in the RTRIE. A large number of dependent reads for every prefix is an undesirable quality of a routing algorithm. Further, one lookup may be distinguished by a single bit in the RTRIE, whereas another lookup in the same RTRIE may require many dependent reads. This variability in lookup time is another undesirable quality in a routing algorithm.
The forwarding engine may also perform IPv6 address lookups by searching an MTRIE. The MTRIE includes a root node which consists of an array that is indexed by a first portion of an IPv6 address. Each array element in the root node can store a pointer that references a corresponding “first-level” node. Thus, a root-node array comprising 2N entries may reference up to 2N different first-level nodes. Each first-level node is an array which is indexed by a second portion of the IPv6 address. Array elements in each first-level node may contain pointers that reference corresponding “second-level” nodes. In this hierarchical manner, successive levels in the MTRIE comprise an exponential number of nodes (i.e., arrays), each of which is indexed by a different portion of the IPv6 address. An IPv6 address lookup therefore involves traversing the MTRIE until an array element is located that contains a pointer to the address's routing information. Array elements “not in use” may store pointers that reference default routing information, or, alternatively, may store degenerate values, such as NULL values.
An MTRIE can hence be constructed such that the number of dependent reads required is bounded to a reasonable number. However, the amount of memory consumed increases dramatically as a consequence of the size of the array that must be allocated at each level. The “stride” (number of bits examined at each level) of an MTRIE may be “tuned” to reduce the memory overhead. Tuning essentially trades off the number of nodes that are expected to be allocated at a particular level for the size of the array at that level. Accordingly, for small array sizes and few MTRIE levels, e.g., as conventionally required for IPv4 address lookups, the MTRIE may be implemented in a reasonable amount of memory. However, for 128-bit IPv6 addresses, the number of MTRIE levels and the amount of memory required to maintain those levels is impractical. As IPv6 is early in its adoption cycle, the distribution of routes cannot be reliably predicted. Hence, variable stride-tuning techniques may be required to implement IPv6 lookups in an MTRIE, and such techniques are generally undesirable. Moreover, the number of dependent MTRIE lookups needed to locate routing information for an IPv6 address may also be prohibitive with regards to processing resources.
Some forwarding engines perform IPv6 address lookups by searching a hash table. The hash table is an array whose entries may be indexed by applying a conventional hash function to an IPv6 address, or a portion thereof. In practice, the process of hashing different addresses may generate the same index into the table thereby resulting in a “collision.” In an ideal scenario, the hash table is large enough to accommodate every IPv6 address stored in the intermediate node and very few collisions would occur. For small address spaces, this can be achieved.
However, in reality, the size of the hash table is limited, e.g., by the node's memory availability, and collisions often occur when the table stores large numbers of IPv6 addresses. Therefore, each hash-table entry may be associated with a corresponding list of colliding addresses. Unfortunately, such a list is typically searched linearly every time the hash-table entry is indexed, often resulting in an unacceptable number of dependent lookups. Furthermore, if the entry's list is configured to store a maximum number of colliding addresses, some addresses may not be able to fit into the list. In this situation, the forwarding engine cannot locate those addresses' routing information through the hash table, and consequently the engine may have to defer the lookup to a backup mechanism.
A forwarding engine may employ a content addressable memory instead of a hash table or trie-based data structure to perform IPv6 address lookups. The CAM is a storage device that includes logic and circuitry for storing data at a memory location defined by the value of the data. Accordingly, the CAM may be configured to store an IPv6 address's routing information at a memory location defined by the value of the IPv6 address.
While a CAM can perform address lookups relatively quickly, it suffers a number of significant disadvantages. For example, the CAM densities are limited, and the number of routes that can be stored has a hard limit (e.g., an 18 Mbit CAM may store 125,000 IPv6 routes with little room for expansion). As a consequence, multiple CAM devices may be required to perform IPv6 address lookups for larger routing tables. In addition, CAMs consume relatively large amounts of electrical power compared to other forms of memory devices, such as dynamic random access memories (DRAM). Further, CAMs are currently more expensive than other conventional storage devices. In sum, for some applications, the disadvantages of implementing CAMs in the forwarding engine outweigh the their ability to perform fast IPv6 address lookups.
Therefore, it is desirable to provide an IPv6 address lookup technique that is deterministic, and that employs fewer dependent lookups and less memory than a hash table or trie-based implementation. In addition, the technique should be capable of performing address lookups for large route densities (e.g., 1,000,000 routes) without consuming excessive amounts of power. The technique also should not punt its operation to other, possibly slower, address lookup algorithms.